Computer systems having a central processing unit (CPU) and memory for storing instructions and data are well known. A typical computer system can have many types of memory that together form a hierarchy, wherein a memory's capacity increases, and speed and cost decrease as one moves down the hierarchy. A cache is a relatively fast, small memory that is used to provide local storage for frequently accessed locations of a larger, relatively slow, main memory. Main memory in turn is relatively faster, smaller and more expensive than magnetic disks or magnetic tape.
Computer programs that run in such a computer system typically use a virtual address to reference operands in memory. The virtual address is translated by the computer system into a physical address that is actually used to retrieve a word from main memory. The address translation from a virtual address to a corresponding physical address involves retrieval of one or more entries, called "table entries", from one or more tables, called "address translation tables." Typically, each table entry includes a high address portion, called a "tag" of the virtual address, a similar tag of the corresponding physical address, and certain status bits, such as an access bit and a dirty bit.
An access to main memory for every address translation limits the CPU's speed in executing any given instruction, as compared to directly using a physical address. To avoid access to main memory for each address translation operation, a limited number of frequently used virtual addresses and their corresponding physical addresses can be stored locally in a memory, commonly referred to as a "translation lookaside buffer" (TLB), and located on the same integrated chip as the CPU.
When a table entry containing a certain virtual address tag is not found in the TLB, i.e. when a TLB "read miss" occurs, a table look up can be performed in a cache on the chip followed by a lookup in main memory. The retrieved table entry is then stored in the TLB, i.e. a TLB "line fill" occurs. A TLB read miss can occur under a variety of conditions, depending on the computer program being executed, and on the algorithm, such as a least recently used (LRU) algorithm, used to overwrite an old entry during a TLB line fill.
When a table look up is performed on a read miss, the CPU may have to wait for not only a slow access to main memory, but even a slower access to magnetic disk, e.g. if only a portion of the address translation table is located in main memory and does not contain the necessary table entry, typically if the CPU switches to execution of a new process. Moreover, the CPU may have to wait even after completion of a table look up, for example to retrieve a word from the addressed location in main memory, and occasionally for retrieval of the word at the addressed location from magnetic disk.